package com.example.demo.arithmetic.algorithm.recursion;

/**
 * 递归实现二分查找
 */
public class BinarySearch {
    public static void main(String[] args) {
        int a = search();
        System.out.println(a);
    }

    public static int search() {
        int m = fatorialSearch(new int[]{1, 2, 3, 4, 5}, 8, 0, 4);
        if (m == -1) {
            return -1;
        } else
            return m;
    }

    private static int fatorialSearch(int[] arr, int target, int start, int end) {
        // 不加这一段代码 找不到的情况无法退出 会栈溢出
        if (start > end) {
            return -1;
        }

        int m = (start + end) >>> 1;
        if (target > arr[m]) {
            return fatorialSearch(arr, target, m + 1, end);
        } else if (target < arr[m]) {
            return fatorialSearch(arr, target, start, m - 1);
        } else
            return m;
    }
}
